从事定量的管理这方面的研究已经有好几年了，研究管理过程中物的优化利用必然涉及到优化算法的设计。从自己读硕读博，到指导学生进行这方面的研究，如何让初涉这个领域的研究生能够轻松理解常见算法的思想，成了我们不可逾越的一个课题。
这段时间在美国访学，很多事情要DIY。这不是吗，前几天自行车前胎没气了，就要自己动手补。突发奇想，若把这个简单的修车过程描述出来，也挺有意思，因此写了这篇日志。朋友们从中可以看到，其实论文中的算法比修自行车要简单。
首先，我们写下修自行车内胎的算法步骤，见算法1。
算法1.自行车前胎修补DIY算法
Step 1.初始化：自行车前胎漏气；
Step 2.寻找合适大小的棍状物，例如筷子；
Step 3.借助于棍状物扒自行车车胎；
Step 4.寻找漏气处。如果破裂处比较小，则转Step 8；（否则，执行下一步）
Step 5.购买新胎和扳手（借扳手亦可）；
Step 6.用扳手讲车轮从轴承处下掉；
Step 7.换内胎；转Step 12；
Step 8.购买车胎的patch kit和胶水；
Step 9.补胎；
Step 10.充气检查。未补好，则转Step 9；（否则，执行下一步）
Step 11.放气；
Step 12.检查外胎是否存在钉子等致使内胎漏气的东西。若有，清除；
Step 13.上外胎；结束。
呵呵，竟然包含了13步之多！
再看看我们在论文中常见的算法，就简单的可怜了。
近些年来比较热的是亚启发式算法，其主要原因是由于计算机的计算处理能力得到了极大的提高。亚启发式算法基本上来源于局部搜索算法（LS，Local Search），其算法思想见算法2。局部搜索算法是一种在当前可行解的基础上，按照一定的方法产生邻域并以该邻域中的最优解作为下一个当前可行解的不断迭代的搜索算法，当算法无法改进某一当前可行解时则算法结束。
算法2.局部搜索算法LS
Step 1.产生一个初始解x，计算对应的目标函数值f(x)；
Step 2.在当前解x的邻域中搜索最好的那一个x’，并对应f(x’)；
Step 3.如果x’优于x（比较f(x)与f(x’)的值），则用x’替换当前解x，转Step 2；（否则，转下一步）
Step 4.将x和对应的f(x)视作最优解和最优值；结束。
作为亚启发式算法的鼻祖，LS具有其先天性的缺陷。很多人发现在用LS解决问题时当当前解是某一局部最优解时往往就难以再继续改进解的质量，人们给这种现象取名叫局部最优陷阱。而后面的亚启发式算法基本上清一色（个别除外）地基于LS的思想，加入了各种不同的跳出或避免陷入局部最优陷阱。以模拟退火算法和可变邻域搜索算法为例说明。
模拟退火（SA，Simulated Annealing）的思想是避免陷入局部最优陷阱，它是对局部搜索算法的一种拓展。从某种意义上看，局部搜索之所以陷入局部最优陷阱是因为它每次迭代总是选择当前解邻域中的局部最优解。然而事实上，一个全局最优解未必在某一当前局部最优解的邻域中。因此模拟退火算法的思想是每次迭代算法以一定的概率接受劣解而不是永远选择邻域中的局部最优解。为了能使算法最终向全局最优解收敛，接受劣解的概率随迭代步数的增加而变小直至接近于0。以目标是最小化形式为例，模拟退火算法描述见算法3。
算法3.模拟退火算法SA
Step 1.生成一个初始可行解x，计算对应的目标函数f(x)；设置降温次数k，设置温度T为初始温度t0和第k次降温对应的温度tk；设置温度tk时搜索执行次数mk；
Step 2.设置当前温度下搜索次数的初始值m=0；
Step 3.在x的邻域中生成一个解x’，计算△=f(x’)-f(x)；
Step 4.如果△0，则用x’替代x；否则在区间[0,1]中随机生成一个随机数§；如果exp(-△/tk)>§，则用x’替代x；m=m+1；如果mmk，则转Step 3；
Step 5. k=k+1；T=tk；若满足终止条件，则返回x及对应的f(x)，结束；否则转Step 2。
SA算法描述虽然复杂了一些，其实就是讲每一步中如果得到了比较差的解，我也有可能接收它，接收的概率随着算法的执行过程从1到0逐渐减小，Step 4中那个看上去很唬人的公式其实就是这个意思。
可变邻域搜索算法（VNS，Variable Neighborhood Search）的思想是跳出局部最优陷阱。可变邻域搜索认为局部搜索之所以陷入局部最优是因为其邻域构造方式不恰当并且仅采用一种邻域生成方法，因此要想获得全局最优解可以设计许多替补邻域生成方式，当第一种邻域生成方式陷入局部最优，可以转而采用第二种邻域生成方式改变搜索空间，直至采用所用的邻域生成方式均无法获得更优的解则算法结束。你不是陷入了局部最优吗，我用另外一种生成邻域的方法，这样搜索的范围发生了改变，也许能搜到更优的吧。不行？我再换一种替补邻域生成方式，我还真不信你跳不出。呵呵，其实